package 链表;
import java.util.HashMap;
import java.util.Map;

/**
 * LRU，Least Recently Used，即最近使用过的数据是有用的，
 * 可以使用双链表+Hashmap解答，双链表用于存储LRUCache的数据，Hashmap实现O（1）的平均时间复杂度
 * 每次从链表尾部添加元素，靠尾的元素就是最近使用过
 * 某个key可以通过哈希表快速定位到节点。
 * @author 翟晓龙
 * @date 2022/4/14
 */
public class LRUCache<T> {

    private Map<String,DoubleNode<T>> caches;

    /**
     * LRU链表
     */
    private DoubleLink<T> doubleLink;

    /**
     * 容量
     */
    private int capacity;

    public LRUCache(int capacity){
        this.caches = new HashMap<>();
        this.doubleLink = new DoubleLink<>();
        this.capacity = capacity;
    }

    /**
     * 缓存查询
     * @param key
     * @return
     */
    public DoubleNode<T> get(String key){
        DoubleNode<T> node = caches.get(key);
        if (node == null){
            return null;
        }
        doubleLink.moveToLast(node);
        return node;
    }

    /**
     * 缓存添加
     * @param key
     * @param value
     */
    public void put(String key,T value){
        DoubleNode<T> node = caches.get(key);
        if (node != null){
            // 已经存在，修改value，节点移到尾部
            node.setValue(value);
            doubleLink.moveToLast(node);
        }else {
            // 添加新节点
            node = new DoubleNode<>(key,value);
            node.setValue(value);
            // 容量调整
            capacityReduce(1);
            doubleLink.addLast(node);
            caches.put(key,node);
        }
    }

    /**
     * 减容量
     * @param num 添加数量
     */
    private void capacityReduce(Integer num){
        int gap = capacity - num;
        if (gap < 0){
            // 淘汰过期数据
            while (gap++ != 0){
                outHeadNode();
            }
        }
        capacity -= num;
    }

    /**
     * 淘汰节点
     */
    private void outHeadNode(){
        DoubleNode node = doubleLink.removeHead();
        if (node == null){
            return;
        }
        caches.remove(node.key);
        capacity ++;
    }

    /**
     * 删除元素
     * @param key
     */
    public DoubleNode<T> delete(String key){
        DoubleNode<T> node = caches.get(key);
        if (node == null){
            return null;
        }
        caches.remove(key);
        doubleLink.remove(node);
        capacity ++;
        return node;
    }


    class DoubleNode<T> {

        private T value;
        private String key;
        private DoubleNode<T> next;
        private DoubleNode<T> pre;

        public DoubleNode(String key,T value){
            this.value = value;
            this.key = key;
        }

        public T getValue() {
            return value;
        }

        public void setValue(T value) {
            this.value = value;
        }

        public DoubleNode<T> getNext() {
            return next;
        }

        public void setNext(DoubleNode<T> next) {
            this.next = next;
        }

        public DoubleNode<T> getPre() {
            return pre;
        }

        public void setPre(DoubleNode<T> pre) {
            this.pre = pre;
        }
    }

    class DoubleLink<T> {

        private DoubleNode<T> head;
        private DoubleNode<T> tail;
        private int size;

        public  DoubleLink(){
            head = new DoubleNode<T>(null,null);
            tail = new DoubleNode<T>(null,null);
            head.next = tail;
            tail.pre = head;
        }

        /**
         * 添加
         * @param node
         */
        public void addLast(DoubleNode<T> node){
            tail.getPre().setNext(node);
            node.setPre(tail.getPre());
            node.setNext(tail);
            tail.setPre(node);
            size ++ ;
        }

        /**
         * 删除指定节点
         * @param node
         */
        public void remove(DoubleNode<T> node){
            node.getPre().setNext(node.next);
            node.getNext().setPre(node.getPre());
            size -- ;
        }

        /**
         * 删除并返回头指针
         * @return
         */
        public DoubleNode<T> removeHead(){
            if (head.next == tail){
                return null;
            }
            DoubleNode<T> headNode = head.next;

            head.next = head.next.next;
            head.next.pre = head;

            headNode.next = null;
            headNode.pre = null;
            size --;
            return headNode;
        }

        public void moveToLast(DoubleNode<T> node){
            remove(node);
            addLast(node);
        }

    }

}
